Various networking devices such as switches and routers are often arranged to buffer network traffic to provide better performance. As the incoming traffic to the network device increases in speed, the processing circuitry in the network device reaches a limit where it cannot process the incoming data fast enough. Instead of discarding the excess traffic, it is buffered and processed later.
Some networking devices have multiple input ports with a single output port. The output port reaches a physical speed limit when the total traffic entering the input ports exceeds the speed of the output port. This type of speed limit is referred to as congestion. When congestion is temporary, the network data packets can be buffered up and then smoothly transmitted over time. However, network data packets can be lost when the congestion persists over long periods of time.
Networking devices often use switch fabrics to transfer data from the ingress ports to egress ports. Buffering is often placed at the ingress ports of the switch fabric. The input buffers may be arranged as first-in first-out (FIFO) queues, or as first-in random-out (FIRO) queues. A FIFO queue that is operated without a scheduling algorithm may cause head-of-line blocking to occur. For example, when ‘k’ packets are buffered in a FIFO queue, only one packet is allowed to pass through, and ‘k−1’ packets must wait for the next cycle. In the meantime, while one of the ‘k−1’ cells waits for its turn, other packets are queued in the buffer and blocked from reaching a possibly idle output port in the switch fabric. To avoid head-of-line blocking, it is generally accepted that the data should be grouped in queues based on the egress port.
When data is buffered at the ingress ports and separated into queues on-behalf of the egress ports, it is referred to as Virtual Output Queuing (VOQ). Some network devices utilize multiple banks of memory to provide buffering. As shown in FIG. 5, multiple (Y) banks of memory may be used to provide multiple virtual output queues. The ingress traffic is analyzed to determine the appropriate output port assignment. Ingress traffic is then buffered in the appropriate queue.